package com.qrpcw.datastructures;

class Node{
	Node next;
	int data;
	public Node(int data){
		this.data = data;
		next = null;
	}
}
	
public class SinglyLinkedList {
	private Node head;
    private Node tail;

    public SinglyLinkedList(){
	    head = null;
	    tail = null;
    }
	
	public void add(Node newNode){
		if (newNode == null){
			 return;
		}else {
			newNode.next = null;
	        if (head == null) {
	            head = newNode;
	            tail = newNode;
	          } else {
	            tail.next = newNode;
	            tail = newNode;
	          }
	    }
	}
	
	public void insertFirst(Node newNode){
		if (newNode == null){
			return;
		}else{
			newNode.next = null;
			if (head == null){
				head = newNode;
				tail = newNode;
			}else{
				newNode.next = head;
				head = newNode;
			}
		}
	}
	
	public void delete(SinglyLinkedList L, int data){
		Node x = L.head;
		Node s = search(L,data);
		while(x.next != s && s != null){
			x = x.next;
		}
		//x is the node before Node a
		x.next = s.next;
	}

	public Node search(SinglyLinkedList L, int data){
		Node x = L.head;
		while(data != x.data && x != null ){
			x = x.next;
		}
		return x;
	}

	public void insertMid(SinglyLinkedList L, Node a, Node newNode){
		if (newNode == null){
			return;
		}else{
			Node s = search(L,a.data);
			newNode.next = s.next;
			s.next = newNode;
		}
	}
	
	public void TraversalPrint(SinglyLinkedList L){
		Node x = L.head;
		while(x != null){
			System.out.print(x.data);
			x = x.next;
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		SinglyLinkedList test = new SinglyLinkedList();
		Node one = new Node(1);
		Node two = new Node(2);
		Node three = new Node(3);
		Node four = new Node(4);
		Node five = new Node(5);
		Node six = new Node(6);
		test.add(one);
		test.add(two);
		test.add(three);
		test.add(four);
		test.add(six);
		test.TraversalPrint(test);
		test.insertMid(test, four, five);
		test.TraversalPrint(test);
		test.delete(test, 2);
		test.insertFirst(new Node(0));
		test.TraversalPrint(test);
	}

}
